/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-median-from-data-stream
   @Language: C++
   @Datetime: 17-04-06 00:01
   */

// Method 1, Using Maxheap and Minheap, Time 74ms
class Solution {
public:
	/**
	 * @param nums: A list of integers.
	 * @return: The median of numbers
	 * Tip: Using Maxheap to record n/2 elements which are smaller
	 *      Using Minheap to record n/2 elements which are bigger
	 *      Then, current median is maxheap.top() or minheap.top()
	 */
	vector<int> medianII(vector<int> &A) {
		// write your code here
		priority_queue<int,vector<int>,less<int> > maxh;
		priority_queue<int,vector<int>,greater<int> > minh;
		vector<int> v(A.size(),0);
		for(int i=0; i<A.size(); ++i){
			if (i&1){   // odd, add to maxh
				if (minh.size() && A[i]>minh.top()){
					maxh.push(minh.top());
					minh.pop();
					minh.push(A[i]);
				}
				else maxh.push(A[i]);
				v[i] = maxh.top();
			}
			else{       // even, add to minh
				if (maxh.size() && A[i]<maxh.top()){
					minh.push(maxh.top());
					maxh.pop();
					maxh.push(A[i]);
				}
				else minh.push(A[i]);
				v[i] = minh.top();
			}
		}
		return v;
	}
};
